package com.cango.student.algorithm.leetcode;

import com.cango.student.algorithm.nodepackage.Node;

import java.util.HashSet;

/**
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 *
 * 还可以用hashset存放
 *
 * linked-list-cycle-ii
 */
public class DetectCycle {
    public Node detectCycle(Node head) {
        if (head == null) return null;
        Node p = head, p2 = head;
        boolean hasCycle = false;
        while (p2.next != null && p2.next.next != null) {
            p = p.next;
            p2 = p2.next.next;
            if (p == p2) {
                hasCycle = true;
                break;
            }
        }

        /**
         * 因为多走了两步，所以从头走，和慢指针开始走，相遇就是开始节点
         */
        if (hasCycle) {
            Node q = head;
            while (p != q) {
                p = p.next;
                q = q.next;
            }
            return q;
        }  else
            return null;
    }

    public Node detectCycle2(Node head) {
        HashSet<Node> set = new HashSet<>();
        Node node = head;
        while(node != null) {
            if (set.contains(node)) {
                return node;
            }
            set.add(node);
            node = node.next;

        }
        return null;
    }
}
